import javafx.util.Pair;

import java.util.*;


public class Solution13 {
    public static void main(String[] args) {
        Solution13 solution = new Solution13();
        List<String> wordList = new ArrayList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");

        int i = solution.ladderLength("hit", "cog", wordList);
        System.out.println(i);
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 如果我们采用字母字典的形式的话，很没必要，造成很多的没有必要的结果，需要进行很多步骤的校验
        // 针对已经给出的字典，如果我们能转换，那么必然经历字典，对于当前的word我们有多少种转换的方式，
        // 对wordList进行预处理
        Map<String,List<String>> wordMap = new HashMap<>();
        Set<String> set = new HashSet<>();
        for(String word:wordList){
            for(int i=0;i<word.length();i++){
                String key = word.substring(0,i)+"*"+word.substring(i+1);
                List<String> values = wordMap.getOrDefault(key,new ArrayList<String>());
                values.add(word);
                wordMap.put(key,values);
            }
        }
        Deque<Pair<String,Integer>> deque = new LinkedList<>();
        deque.add(new Pair<>(beginWord,1));
        while(!deque.isEmpty()){
            Pair<String, Integer> poll = deque.poll();
            String pollKey = poll.getKey();
            Integer level = poll.getValue();
            for(int i=0;i<pollKey.length();i++){
                String temp = pollKey.substring(0,i)+"*"+pollKey.substring(i+1);
                List<String> changeList = wordMap.get(temp);
                if(null==changeList)continue;
                for(String change:changeList){
                    if(endWord.equals(change)){
                        return level+1;
                    }
                    if(!set.contains(change)){
                        deque.add(new Pair<>(change,level+1));
                        set.add(change);
                    }
                }
            }
        }
        return 0;
    }
}
